C1. Magnitude (Easy Version)

给你一个长度为 $n$ 的数组 $a$ 。从 $c = 0$ 开始。然后，对从 $1$ 到 $n$ 的每个 $i$ （按递增顺序）做以下***中的一个：

选项 $1$ ：将 $c$ 设为 $c + a_{i}$ 。
选项 $2$ ：将 $c$ 设为 $| c + a_{i} |$ 。

设上述步骤后 $c$ 的最大终值等于 $k$ 。求出 $k$ 。

官方题解：

我们只需要选择一次 $2$ 选项。为什么？假设我们不止一次选择了 $2$ ，那么考虑一下最后两次的选择。当 $c + a_{i}$ 为负数时，这两次都必须发生，否则就没有理由选择 $2$ 而不是 $1$ 。因此，如果我们在第一次操作中选择了 $1$ 而不是 $2$ ，这将导致第二次操作前 $c$ 的值减小。由于它是负值，这就增加了幅度，因此在第一次操作中选择 $1$ 是更优的选择。

因为我们只需要使用一次选项 $2$ ，所以我们可以蛮力使用该操作，并用前缀和计算 $c$ 的最终值。

即在 前缀和最小的位置且那个位置小于 0 使用操作 2，如果多次使用了操作 2 会导致反而变小。

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)pre[i] = pre[i - 1] + a[i];
    int ans = pre[n];
    for (int i = 1;i <= n;i++) {
        if (pre[i] < 0) {
            ans = max(ans, pre[n] - 2 * pre[i]);
        }
    }
    cout << ans << '\n';

}

设 $f_{i, 0 / 1}$ 代表前 $i$ 个能达到的最大值/最小值

只需要维护最大值和最小值即可。

当前的最大值要么就是前 $i - 1$ 项的最大值加上 $a_{i}$ 得到，要么是前 $i - 1$ 项的最小值加上 $a_{i}$ 取绝对值得到。

最小值则是前 $i - 1$ 项的最小值加上 $a_{i}$

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];

    vector<array<int, 2>> f(n + 1);
    for (int i = 1;i <= n;i++) {
        f[i][0] = max(abs(f[i - 1][1] + a[i]), abs(f[i - 1][0] + a[i]));
        f[i][1] = f[i - 1][1] + a[i];
    }
    cout << max(f[n][1], f[n][0]) << '\n';
}